home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2008 February / PCWFEB08.iso / Software / Resources / Developers / XAMPP 1.5.4 / Windows installer / xampp-win32-1.5.4-installer.exe / xampp / php / pear / FSM.php < prev    next >
Encoding:
PHP Script  |  2006-04-07  |  9.9 KB  |  296 lines
  1. <?php
  2. /* vim: set expandtab softtabstop=4 tabstop=4 shiftwidth=4: */
  3. /*
  4.  * Copyright (c) 2002-2006 Jon Parise <jon@php.net>
  5.  *
  6.  * Permission is hereby granted, free of charge, to any person obtaining a copy
  7.  * of this software and associated documentation files (the "Software"), to
  8.  * deal in the Software without restriction, including without limitation the
  9.  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  10.  * sell copies of the Software, and to permit persons to whom the Software is
  11.  * furnished to do so, subject to the following conditions:
  12.  *
  13.  * The above copyright notice and this permission notice shall be included in
  14.  * all copies or substantial portions of the Software.
  15.  *
  16.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22.  * IN THE SOFTWARE.
  23.  *
  24.  * $Id: FSM.php,v 1.14 2006/01/19 06:36:19 jon Exp $
  25.  */
  26.  
  27. /**
  28.  * This class implements a Finite State Machine (FSM).
  29.  *
  30.  * In addition to maintaining state, this FSM also maintains a user-defined
  31.  * payload, therefore effectively making the machine a Push-Down Automata
  32.  * (a finite state machine with memory).
  33.  *
  34.  * This code is based on Noah Spurrier's Finite State Machine (FSM) submission
  35.  * to the Python Cookbook:
  36.  *
  37.  *      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262
  38.  *
  39.  * @author  Jon Parise <jon@php.net>
  40.  * @version $Revision: 1.14 $
  41.  * @package FSM
  42.  * @license http://www.opensource.org/licenses/mit-license.php MIT License
  43.  *
  44.  * @example rpn.php     A Reverse Polish Notation (RPN) calculator.
  45.  */
  46. class FSM
  47. {
  48.     /**
  49.      * Represents the initial state of the machine.
  50.      *
  51.      * @var string
  52.      * @see $_currentState
  53.      * @access private
  54.      */
  55.     var $_initialState = '';
  56.  
  57.     /**
  58.      * Contains the current state of the machine.
  59.      *
  60.      * @var string
  61.      * @see $_initialState
  62.      * @access private
  63.      */
  64.     var $_currentState = '';
  65.  
  66.     /**
  67.      * Contains the payload that will be passed to each action function.
  68.      *
  69.      * @var mixed
  70.      * @access private
  71.      */
  72.     var $_payload = null;
  73.  
  74.     /**
  75.      * Maps (inputSymbol, currentState) --> (action, nextState).
  76.      *
  77.      * @var array
  78.      * @see $_initialState, $_currentState
  79.      * @access private
  80.      */
  81.     var $_transitions = array();
  82.  
  83.     /**
  84.      * Maps (currentState) --> (action, nextState).
  85.      *
  86.      * @var array
  87.      * @see $_inputState, $_currentState
  88.      * @access private
  89.      */
  90.     var $_transitionsAny = array();
  91.  
  92.     /**
  93.      * Contains the default transition that is used if no more appropriate
  94.      * transition has been defined.
  95.      *
  96.      * @var array
  97.      * @access private
  98.      */
  99.     var $_defaultTransition = null;
  100.  
  101.  
  102.     /**
  103.      * This method constructs a new Finite State Machine (FSM) object.
  104.      *
  105.      * In addition to defining the machine's initial state, a "payload" may
  106.      * also be specified.  The payload represents a variable that will be
  107.      * passed along to each of the action functions.  If the FSM is being used
  108.      * for parsing, the payload is often a array that is used as a stack.
  109.      *
  110.      * @param   string  $initialState   The initial state of the FSM.
  111.      * @param   mixed   $payload        A payload that will be passed to each
  112.      *                                  action function.
  113.      */
  114.     function FSM($initialState, &$payload)
  115.     {
  116.         $this->_initialState = $initialState;
  117.         $this->_currentState = $initialState;
  118.         $this->_payload = &$payload;
  119.     }
  120.  
  121.     /**
  122.      * This method resets the FSM by setting the current state back to the
  123.      * initial state (set by the constructor).
  124.      */
  125.     function reset()
  126.     {
  127.         $this->_currentState = $this->_initialState;
  128.     }
  129.  
  130.     /**
  131.      * This method adds a new transition that associates:
  132.      *
  133.      *      (symbol, currentState) --> (nextState, action)
  134.      *
  135.      * The action may be set to NULL, in which case the processing routine
  136.      * will ignore the action and just set the next state.
  137.      *
  138.      * @param   string  $symbol         The input symbol.
  139.      * @param   string  $state          This transition's starting state.
  140.      * @param   string  $nextState      This transition's ending state.
  141.      * @param   string  $action         The name of the function to invoke
  142.      *                                  when this transition occurs.
  143.      *
  144.      * @see     addTransitions()
  145.      */
  146.     function addTransition($symbol, $state, $nextState, $action = null)
  147.     {
  148.         $this->_transitions["$symbol,$state"] = array($nextState, $action);
  149.     }
  150.  
  151.     /**
  152.      * This method adds the same transition for multiple different symbols.
  153.      *
  154.      * @param   array   $symbols        A list of input symbols.
  155.      * @param   string  $state          This transition's starting state.
  156.      * @param   string  $nextState      This transition's ending state.
  157.      * @param   string  $action         The name of the function to invoke
  158.      *                                  when this transition occurs.
  159.      *
  160.      * @see     addTransition()
  161.      */
  162.     function addTransitions($symbols, $state, $nextState, $action = null)
  163.     {
  164.         foreach ($symbols as $symbol) {
  165.             $this->addTransition($symbol, $state, $nextState, $action);
  166.         }
  167.     }
  168.  
  169.     /**
  170.      * This method adds a new transition that associates:
  171.      *
  172.      *      (currentState) --> (nextState, action)
  173.      *
  174.      * The processing routine checks these associations if it cannot first
  175.      * find a match for (symbol, currentState).
  176.      *
  177.      * @param   string  $state          This transition's starting state.
  178.      * @param   string  $nextState      This transition's ending state.
  179.      * @param   string  $action         The name of the function to invoke
  180.      *                                  when this transition occurs.
  181.      *
  182.      * @see     addTransition()
  183.      */
  184.     function addTransitionAny($state, $nextState, $action = null)
  185.     {
  186.         $this->_transitionsAny[$state] = array($nextState, $action);
  187.     }
  188.  
  189.     /**
  190.      * This method sets the default transition.  This defines an action and
  191.      * next state that will be used if the processing routine cannot find a
  192.      * suitable match in either transition list.  This is useful for catching
  193.      * errors caused by undefined states.
  194.      *
  195.      * The default transition can be removed by setting $nextState to NULL.
  196.      *
  197.      * @param   string  $nextState      The transition's ending state.
  198.      * @param   string  $action         The name of the function to invoke
  199.      *                                  when this transition occurs.
  200.      */
  201.     function setDefaultTransition($nextState, $action)
  202.     {
  203.         if (is_null($nextState)) {
  204.             $this->_defaultTransition = null;
  205.             return;
  206.         }
  207.  
  208.         $this->_defaultTransition = array($nextState, $action);
  209.     }
  210.  
  211.     /**
  212.      * This method returns (nextState, action) given an input symbol and
  213.      * state.  The FSM is not modified in any way.  This method is rarely
  214.      * called directly (generally only for informational purposes).
  215.      *
  216.      * If the transition cannot be found in either of the transitions lists,
  217.      * the default transition will be returned.  Note that it is possible for
  218.      * the default transition to be set to NULL.
  219.      *
  220.      * @param   string  $symbol         The input symbol.
  221.      *
  222.      * @return  mixed   Array representing (nextState, action), or NULL if the
  223.      *                  transition could not be found and not default
  224.      *                  transition has been defined.
  225.      */
  226.     function getTransition($symbol)
  227.     {
  228.         $state = $this->_currentState;
  229.  
  230.         if (!empty($this->_transitions["$symbol,$state"])) {
  231.             return $this->_transitions["$symbol,$state"];
  232.         } elseif (!empty($this->_transitionsAny[$state])) {
  233.             return $this->_transitionsAny[$state];
  234.         } else {
  235.             return $this->_defaultTransition;
  236.         }
  237.     }
  238.  
  239.     /**
  240.      * This method is the main processing routine.  It causes the FSM to
  241.      * change states and execute actions.
  242.      *
  243.      * The transition is determined by calling getTransition() with the
  244.      * provided symbol and the current state.  If no valid transition is found,
  245.      * process() returns immediately.
  246.      *
  247.      * The action callback may return the name of a new state.  If one is
  248.      * returned, the current state will be updated to the new value.
  249.      *
  250.      * If no action is defined for the transition, only the state will be
  251.      * changed.
  252.      *
  253.      * @param   string  $symbol         The input symbol.
  254.      *
  255.      * @see     processList()
  256.      */
  257.     function process($symbol)
  258.     {
  259.         $transition = $this->getTransition($symbol);
  260.  
  261.         /* If a valid array wasn't returned, return immediately. */
  262.         if (!is_array($transition) || (count($transition) != 2)) {
  263.             return;
  264.         }
  265.  
  266.         /* Update the current state to this transition's exit state. */
  267.         $this->_currentState = $transition[0];
  268.  
  269.         /* If an action for this transition has been specified, execute it. */
  270.         if (!empty($transition[1])) {
  271.             $state = call_user_func_array($transition[1],
  272.                                           array($symbol, &$this->_payload));
  273.  
  274.             /* If a new state was returned, update the current state. */
  275.             if (!empty($state) && is_string($state)) {
  276.                 $this->_currentState = $state;
  277.             }
  278.         }
  279.     }
  280.  
  281.     /**
  282.      * This method processes a list of symbols.  Each symbol in the list is
  283.      * sent to process().
  284.      *
  285.      * @param   array   $symbols        List of input symbols to process.
  286.      */
  287.     function processList($symbols)
  288.     {
  289.         foreach ($symbols as $symbol) {
  290.             $this->process($symbol);
  291.         }
  292.     }
  293. }
  294.  
  295. ?>
  296.